// Copyright (c) Microsoft Corporation
// All rights reserved

namespace Microsoft.Windows.Controls.Specialized.TextModel
{
    using System;
    using System.Text;
    using System.Diagnostics;
    using System.Collections.Generic;

    /// <summary>
    /// A frozen buffer acts exactly like a Text Buffer that's been frozen at a specific time (version)
    /// 
    /// Properties of the frozen buffer are identical to the properties of the original buffer at the time the 
    /// snap-shot was taken.  However we don't store local copies of the buffer at the specified version.
    /// Instead, we compute it dynamically, in order to reduce over-head of keeping multiple copies of the 
    /// buffer around.
    /// </summary>
    class FrozenBuffer : ITextReader
    {
        #region Private Members

        private ITextBuffer _textBuffer;
        private ITextVersion _textVersion;
        private int _bufferLength = -1;
        private int _bufferLineCount = -1;
        private string _text;

        #endregion // Private Members

        /// <summary>
        /// Construct a frozen buffer that acts like a snapshot of the original buffer at a given point of 
        /// time (version)
        /// </summary>
        public FrozenBuffer(ITextBuffer buffer, ITextVersion version)
        {
            _textBuffer = buffer;
            _textVersion = version;

            // If we have been frozen at the current version, we might as well cache some members
            if (_textBuffer.Version == version)
            {
                _bufferLength = _textBuffer.Length;
                _bufferLineCount = _textBuffer.LineCount;
            }
        }

        #region Exposed Methods

        /// <summary>
        /// Gets the text from the buffer at the time it was frozen
        /// </summary>
        /// <param name="startIndex">
        /// The index to start the string fetch from
        /// </param>
        /// <param name="length">
        /// The length of characters to fetch
        /// </param>
        /// <returns>
        /// A string from the frozen buffer
        /// </returns>
        public string GetText(int startIndex, int length)
        {
            // Do we have a cached copy?
            if (_text != null)
                return _text.Substring(startIndex, length);
            else
            {
                // We need to get back to the version at the time the snap-shot was taken
                if (startIndex < 0 || startIndex > this.Length)
                    throw new ArgumentOutOfRangeException("startIndex");

                if (startIndex + length > this.Length)
                    throw new ArgumentOutOfRangeException("length");

                return UnwindChanges(startIndex, length);
            }
        }

        /// <summary>
        /// Gets the text from the buffer at the time it was frozen
        /// </summary>
        /// <param name="startIndex">
        /// The index to start the string fetch from
        /// </param>
        /// <returns>
        /// A string from the frozen buffer
        /// </returns>
        public string GetText(int startIndex)
        {
            // Do we have a cached copy?
            if (_text != null)
                return _text.Substring(startIndex);
            else
            {
                // We need to get back to the version at the time the snap-shot was taken
                if (startIndex < 0 || startIndex > this.Length)
                    throw new ArgumentOutOfRangeException("startIndex");

                return UnwindChanges(startIndex, this.Length - startIndex);
            }
        }

        /// <summary>
        /// Gets the text from the buffer at the time it was frozen
        /// </summary>
        /// <returns>
        /// A string from the frozen buffer
        /// </returns>
        public string GetText()
        {
            // Do we have a cached copy?
            if (_text != null)
                return _text;
            else
            {
                // We need to get back to the version at the time the snap-shot was taken
                // 
                // Also, keep a cache of the text around, so that when GetText is called a second time, 
                // unwinding is not necessary.
                _text = UnwindChanges(0, this.Length);
                return _text;
            }
        }

        /// <summary>
        /// Get a specific character from the text.
        /// </summary>
        public char GetChar(int index) 
        {
            if (_text != null)
                return _text[index];
            else
            {
                _text = UnwindChanges(0, this.Length);
                return _text[index];
            }
        }

        /// <summary>
        /// Gets the text from the buffer at the time it was frozen
        /// </summary>
        /// <param name="startIndex">
        /// The index to start the string fetch from
        /// </param>
        /// <param name="length">
        /// The length of characters to fetch
        /// </param>
        /// <returns>
        /// A character array that represents the requested text
        /// </returns>
        public char[] ToCharArray(int startIndex, int length)
        {
            return GetText(startIndex, length).ToCharArray();
        }

        /// <summary>
        /// Gets the text from the buffer at the time it was frozen
        /// </summary>
        /// <returns>
        /// A character array that represents the requested text
        /// </returns>
        public char[] ToCharArray()
        {
            return GetText().ToCharArray();
        }

        /// <summary>
        /// Copies text from the buffer to a destination character array.
        /// </summary>
        /// <param name="sourceIndex">
        /// The starting index of the text to copy from
        /// </param>
        /// <param name="destination">
        /// The destination character array
        /// </param>
        /// <param name="destinationIndex">
        /// The index in the character array to start copying into
        /// </param>
        /// <param name="count">
        /// The number of characters to copy
        /// </param>
        public void CopyTo(int sourceIndex, char[] destination, int destinationIndex, int count)
        {
            // First get the string and then copy it to the destination
            string ret = GetText(sourceIndex, count);

            ret.CopyTo(0, destination, destinationIndex, count);
        }

        #endregion // Exposed Methods

        #region Exposed Properties

        /// <summary>
        /// Gets the document type for the text this buffer contains
        /// </summary>
        public string DocumentType
        {
            get
            {
                return _textBuffer.DocumentType;
            }
        }

        /// <summary>
        /// Gets the length of the text in the text buffer
        /// </summary>
        public int Length
        {
            get
            {
                if (_bufferLength == -1)
                {
                    _bufferLength = _textBuffer.Length;

                    // We have to walk through the change list apply changes in length to the current count
                    for (ITextVersion v = _textVersion; v != _textBuffer.Version; v = v.Next)
                    {
                        _bufferLength -= v.Change.Delta;
                    }
                }

                return _bufferLength;
            }
        }

        /// <summary>
        /// Gets the number of lines in the text in the text buffer
        /// 
        /// Note: In certain cases this may not be the precise line count.  For more information look at 
        /// remarks.
        /// </summary>
        /// <remarks>
        /// We calculate the line count by tracking back the changes that happened from the current version
        /// of the buffer to the point when the "freeze" happened.  In such a case, if a change had happened
        /// that involves merging or splitting of a cr/lf sequence, we may not be returning the exact line 
        /// count.  However since this is pretty rare, we aren't willing to take the perf hit that we'll 
        /// incur trying to scan all such changes.
        /// </remarks>
        public int LineCount
        {
            get
            {
                if (_bufferLineCount == -1)
                {
                    _bufferLineCount = _textBuffer.LineCount;

                    // We have to walk through the change list apply changes in line count 
                    // to the current count
                    // NOTE: This may not be precise in cases where a change happens in between a crlf.
                    // What do we do in that case?  It is probably too expensive to get the entire 
                    // text and compute the line count.
                    for (ITextVersion v = _textVersion; v != _textBuffer.Version; v = v.Next)
                    {
                        _bufferLineCount -= LinkBuffer.ScanForLineCount(v.Change.NewText);
                        _bufferLineCount += LinkBuffer.ScanForLineCount(v.Change.OldText);
                    }
                }

                return _bufferLineCount;
            }
        }

        /// <summary>
        /// Gets the Text Version associated with this Text Reader
        /// </summary>
        public ITextVersion Version
        {
            get
            {
                return _textVersion;
            }
        }

        #endregion // Exposed Properties

        #region Private Helpers

        /// <summary>
        /// Unwinds changes to the buffer keeping track only of the specified block
        /// of text.
        /// </summary>
        /// <param name="startPosition">
        /// The start position of the text
        /// </param>
        /// <param name="length">
        /// The length of the string to be extracted
        /// </param>
        private string UnwindChanges(int startPosition, int length)
        {
            // If the versions are the same, return immediately
            if (_textVersion == _textBuffer.Version)
            {
                _bufferLength = _textBuffer.Length;
                _bufferLineCount = _textBuffer.LineCount;
                return _textBuffer.GetText(startPosition, length);
            }

            // Keep a copy of the length to check at the very end
            int oldLength = length;
            Stack<TextChange> overlaps = new Stack<TextChange>();

            // Algorithm description:
            // Between the "frozen" buffer (us) and the current state of the buffer, there is a list of
            // change records.  We visit each of these changes, in order of occurance, looking for changes
            // which affect the range of text given to us (the "reference range").  For each such change, 
            // we adjust the starting position and length such that, after visiting all changes, the position 
            // and length emcompasses all remaining text in the current buffer.  Also for each such change, 
            // we push a record on a stack that represents the change, so that it can later be reversed.
            //
            // Once this walk is complete, the text in the adjusted range is extracted from the current
            // buffer (if any), and then each adjusted change is popped from the stack and applied to
            // that text, thereby "undoing" the edits that occurred since the buffer was frozen.
            //
            // The result is the text in the reference range, at the time the buffer was frozen.
            for (ITextVersion v = _textVersion; v != _textBuffer.Version; v = v.Next)
            {
                // Version can't be null
                Debug.Assert(v != null);

                // If the change happened upstream from us, ignore it
                if (v.Change.Position >= startPosition + length)
                    continue;

                if (v.Change.OldEnd <= startPosition)
                {
                    startPosition += v.Change.Delta;
                }
                else
                {
                    // There are three cases here.
                    // Case 1: The replace operation started before the reference range.  In this case,
                    //         we don't undo the insertion part; instead we adjust the reference range
                    //         and undo only the deletion.  (The inserted text is not included in the text
                    //         we extract from the current buffer).
                    // Case 2: The replace started within the reference range, and ended beyond it.  Similar
                    //         to case 1, we don't bother undoing the insertion part, but instead adjust
                    //         the reference range appropriately and record an undo of the deletion portion.
                    // Case 3: The replace operation happened within the text we're interested in.  In this
                    //         case, we need to undo both the insertion and deletion.
                    if (v.Change.Position <= startPosition)
                    {
                        // This is case 1
                        int overlap = Math.Min(length, v.Change.OldEnd - startPosition);

                        // Create a change record that will un-delete the appropriate text from the reference 
                        // range.
                        TextChange overlapChange = new TextChange(0, v.Change.OldText.Substring(startPosition - v.Change.Position, overlap), "");
                        overlaps.Push(overlapChange);

                        // Now, update the start position and length of the reference range
                        startPosition += (v.Change.Delta + overlap);
                        length -= overlap;
                    }
                    else
                    {
                        if (v.Change.OldEnd > startPosition + length)
                        {
                            // This is case 2.  Again, create only an undo change for the deletion.
                            int overlap = Math.Min(startPosition + length, v.Change.OldEnd) - v.Change.Position;
                            TextChange overlapChange = new TextChange(v.Change.Position - startPosition, v.Change.OldText.Substring(0, overlap), "");
                            overlaps.Push(overlapChange);

                            // Update the length of the reference range (the position doesn't change).
                            length -= overlap;
                        }
                        else
                        {
                            // This is case 3.  The undo change record is almost an exact copy of the original, 
                            // updated to reflect the position relative to the reference range instead of the 
                            // buffer.
                            TextChange overlapChange = new TextChange(v.Change.Position - startPosition, v.Change.OldText, v.Change.NewText);
                            overlaps.Push(overlapChange);

                            // Update the length (again, position doesn't change)
                            length += v.Change.Delta;
                        }
                    }

                    // If our reference range becomes zero length, we can stop looking at changes.  This is 
                    // because no further edit could possibly change the "starting point" for re-creating the 
                    // reference range text.  Interestingly, even the starting position of the reference range 
                    // is no longer interesting; the entire reference range text will be reconstructed from 
                    // undo records which we've already pushed on the stack, and each of those undo records 
                    // have positions relative to the reference range, not the buffer.
                    if (length == 0)
                        break;
                }
            }

            // Now, that we've transformed our co-ordinates, let's reapply the changes
            // back
            string ret = ReapplyChanges(startPosition, length, overlaps);

            // Make sure we have the right length
            Debug.Assert(ret.Length == oldLength);
            return ret;
        }

        /// <summary>
        /// Re-applies the unwound changes back to the reference string
        /// </summary>
        private string ReapplyChanges(int startPosition, int length, Stack<TextChange> overlaps)
        {
            StringBuilder sb;
            if (length == 0)
                sb = new StringBuilder();
            else
                sb = new StringBuilder(_textBuffer.GetText(startPosition, length));

            while (overlaps.Count > 0)
            {
                TextChange change = overlaps.Pop();

                // Simply delete the new string and insert the old string
                sb.Remove(change.Position, change.NewText.Length);
                sb.Insert(change.Position, change.OldText);
            }

            return sb.ToString();
        }

        #endregion // Private Helpers
    }
}
